#include "Heap.h"


void HeapInit(Hp* p)
{
	assert(p);
	p->data = NULL;

	//如果size初值为 0 则指向下一个位置，如果为-1，则指向当前位置
	p->size = 0; 

	p->capacity = 0;
}

void HeapDestroy(Hp* p)
{
	assert(p);
	free(p->data);
	p->size = 0;
	p->capacity = 0;
}

void HeapShow(Hp* p)
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n");
}


bool HeapEmpty(Hp* p)
{
	assert(p);
	return p->size == 0;
}

void Swap(HDataType* n1, HDataType* n2)
{
	HDataType tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

void BigAdjustUp(Hp* p, int child)
{
	assert(p->data);
	
	//运用完全二叉树的公式，父节点下标 = (子节点下标- 1) / 2
	int parent = (child - 1) / 2;

	while (child > 0) //当走到根节点就结束了即child = 0
	{
		if (p->data[child] > p->data[parent])
		{
			Swap(&p->data[child], p->data[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void HeapPush(Hp* p, HDataType x)
{
	assert(p);

	//首先判断是否需要扩容
	if (p->size == p->capacity)
	{
		int newCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		HDataType* newData = (HDataType*)realloc(p->data, sizeof(HDataType) * newCapacity);
		
		if (newData == NULL) // 如果扩容失败了，退出程序
		{
			printf("realloc failed!\n");
			exit(-1);
		}
		
		p->data = newData;
		p->capacity = newCapacity;
	}

	//然后插入数据
	p->data[p->size] = x;
	p->size++;

	//最后进行调整
	BigAdjustUp(p, p->size - 1);
	
}

void BigAdjustDown(Hp* p, int parent, int size)
{
	assert(p->data);
	
	int child = parent * 2 + 1; //此节点为左孩子
	while (child < size)  //节点必须合法
	{
		//寻找左右孩子中较大的那个节点
		if (child + 1 < size //防止越界
			&& p->data[child] < p->data[child + 1])
			child = child + 1;

		//在大根堆中，如果父节点小于子节点值
		if (p->data[parent] < p->data[child])
		{
			Swap(&p->data[parent], &p->data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapPop(Hp* p)
{
	assert(p);
	
	//先判断堆是否为空
	assert(p->size > 0);

	//然后交换根节点和堆中最后一个节点的数据，并删掉最后一个节点
	Swap(&p->data[0], &p->data[p->size - 1]);
	p->size--;

	//最后进行调整，满足根的性质
	BigAdjustDown(p, 0, p->size);
}

HDataType HeapTop(Hp* p)
{
	assert(p);
	assert(!HeapEmpty(p));
	return p->data[0];
}

int HeapSize(Hp* p)
{
	assert(p);
	return p->size;
}